package algorithm.sort;


/**
 * https://blog.csdn.net/zou_albert/article/details/107405455
 */
public class QuickSort{

	static int temp;
	
	public static void quickSort(int[] arr,int left,int right){	
		if(left > right || left >= arr.length || right < 0)
			return;
		int i = left;
		int j = right;
//		int key = arr[left];
		//三数取中优化
		int key = selectPivotMedianOfThreeAndMoveToLeft(arr, left, right);
		while( i != j ){
			while( arr[j] >= key && i < j )
				j--;
			while( arr[i] <= key && i < j )
				i++;
			if( i < j ){
				swap( arr, i, j );
			}
		}
		//最终将基准数归位
		temp = arr[left];
		arr[left] = arr[i];
		arr[i] = temp;

		quickSort(arr, left, i-1);
		quickSort(arr, i+1, right);		
	}


	/*函数作用：取待排序序列中low、mid、high三个位置上数据，选取他们中间的那个数据作为枢轴*/
	static int selectPivotMedianOfThreeAndMoveToLeft(int[] arr, int low, int high) {
		int mid = low + ((high - low) >> 1);//计算数组中间的元素的下标

		//使用三数取中法选择枢轴
		//目标: arr[mid] <= arr[high]
		if (arr[mid] > arr[high]){
			swap(arr, mid, high);
		}
		//目标: arr[low] <= arr[high]
		if (arr[low] > arr[high]){
			swap(arr, low, high);
		}
		//目标: arr[low] >= arr[mid]
		if (arr[mid] > arr[low]) {
			swap(arr, mid, low);
		}
		//此时，arr[mid] <= arr[low] <= arr[high]
		return arr[low];
		//low的位置上保存这三个位置中间的值
		//分割时可以直接使用low位置的元素作为枢轴，而不用改变分割函数了
	}


	static void swap(int[] arr, int i, int j){
		temp = arr[j];
		arr[j] = arr[i];
		arr[i] = temp;
	}

	public static void main(String[] args) {
		int[] arr=new int[]{2,10,1,9,3,8,4,6,5,5,5};
//		int[] arr=new int[]{7,7,7,7,7,8,4,6,5,5,5};
//		int[] arr=new int[]{7,7,7,7,7,5,4,6,5,5,8};
		quickSort(arr,0,arr.length-1);
		for(int i:arr)
			System.out.print(i+",");
	}
}